package 典型.回溯法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 允许重复用同一个位置的值的组合获取，和为固定一个值  https://leetcode-cn.com/problems/combination-sum/
public class LC39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates.length==0) return  null;
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        Arrays.sort(candidates);//找值得的时候无序数组记得进行排序
        findList(res,list,candidates,target,0);
        return res;
    }
    public void findList( List<List<Integer>> res , List<Integer> list,int[] candidates, int target,int num){
        if(target==0){
            res.add(list);
            return;
        }
        if(target<candidates[num]) return;
        for(int i=num;i<candidates.length&&candidates[i]<=target;i++){
            List<Integer> list1 = new ArrayList<Integer>(list);
            //用深拷贝可以改变list中的值而不是改变引用
            list1.add(candidates[i]);
            findList(res,list1,candidates,target-candidates[i],i);
        }
    }
}


